package microsfot.java;

import java.util.HashMap;
import java.util.Map;

public class MinStackWithMap {
	private Map<Integer,Integer> stack=new HashMap<Integer,Integer>();
	private Integer index=0;
	
	class Entry{
		public Integer min;
		public Integer diff;
		
		public Entry(Integer min,Integer diff){
			this.min=min;
			this.diff=diff;
		}
	}
	public MinStackWithMap push(int element){
		if(stack.isEmpty()){
			stack.put(index++, element);
			stack.put(index++, element);
		}else{
			Integer last=this.pop();
			int diff=element-last;
			stack.put(index++,diff);
			stack.put(index++,diff<0?element:last);
		}
		return this;
	}
	
	public Integer pop(){
		int last=stack.remove(--index);
		int diff=stack.remove(--index);
		
		if(diff<0){
			return last-diff;
		}else{
			if(!this.isEmpty()){
				stack.put(index++,last);
				return last+diff;
			}else{
				stack.put(index++, last);
				return last;
			}
		}
	}
	
	public boolean isEmpty(){
		return stack.isEmpty();
	}
	
	public static void main(String[] args) {
		MinStackWithMap stack=new MinStackWithMap();
		stack.push(3).push(1).push(4).push(0);
		while(!stack.isEmpty()){
			Integer value=stack.pop();
			System.out.println(value);
		}
	}
}
